import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Test {
}
class Solution {
    public int rangeSum(int[] nums, int n, int left, int right) {
        int MOD = (int)1e9 + 7;
        int index = 0;
        int[] ret = new int[n*(n+1)/2];
        for(int i=0; i<n; i++){
            int sum = 0;
            for(int j=i; j<n; j++){
                sum += nums[j];
                ret[index++] = sum;
            }
        }
        Arrays.sort(ret);
        int ans = 0;
        for(int i=left-1; i<right; i++){
            ans = (ans + ret[i])%MOD;
        }
        return ans;
    }
}
class Solution1 {
    static final int MOD = 1000000007;
    public int rangeSum(int[] nums, int n, int left, int right) {
        int[] preSum = new int[n+1];
        for(int i=0; i<n; i++){
            preSum[i+1] = preSum[i] + nums[i];
        }
        int[] prePreSum = new int[n+1];
        for(int i=0; i<n; i++){
            prePreSum[i+1] = prePreSum[i] + preSum[i+1];
        }
        return (getSum(preSum,prePreSum,n,right)-getSum(preSum,prePreSum,n,left-1))%MOD;
    }
    private int getSum(int[] preSum, int[] prePreSum, int n, int k){//得到前k个值的和
        int num = getK(preSum,n,k);
        int sum = 0,count = 0;
        for(int i=0, j=1; i<n; i++){
            while(j<=n && preSum[j]-preSum[i] < num){
                j++;
            }
            j--;
            sum = (sum + prePreSum[j] - prePreSum[i] - (j - i)*preSum[i])%MOD;
            count += j - i;
        }
        sum = (sum + num*(k-count))%MOD;
        return sum;
    }
    private int getK(int[] preSum, int n, int k){
        int left = 0;
        int right = preSum[n];
        while(left <= right){
            int mid = (left+right)/2;
            int count = getCount(preSum,n,mid);
            if(count < k){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
    private int getCount(int[] preSum, int n,int x){
        int count = 0;
        int j = 1;
        for(int i=0; i<n; i++){
            while(j <= n && preSum[j] - preSum[i] <= x){
                j++;
            }
            j--;
            count += j-i;
        }
        return count;
    }


}
